package stu.day48;

public class WordDictionary {

    class Treenode{
        boolean flag = false;
        Treenode[] children = new Treenode[26];
    }

    Treenode root;

    public WordDictionary() {
        root = new Treenode();
    }

    public void addWord(String word) {

        Treenode node = root;
        for(char ch:word.toCharArray()){
            int num = ch - 'a';
            if(node.children[num]==null){
                node.children[num]=new Treenode();
            }
            node = node.children[num];
        }
        node.flag = true;

    }



    public boolean search(String word) {

        return dfs(word,root,0);

    }

    public boolean dfs(String word,Treenode node,int num){

        if(node==null) return false;

        if(num==word.length()){
            return node.flag;
        }

        char ch = word.charAt(num);
        if(ch=='.'){
            for(int i=0;i<26;i++){
                if(dfs(word,node.children[i],num+1)){
                    return true;
                };
            }

        }else {
            int m = ch - 'a';
            return dfs(word,node.children[m],num+1);
        }

        return false;

    }


}
